import functools


class Solution(object):
    def kInversePairs(self, n, k):
        base = 10 ** 9 + 7
        @functools.cache
        def dfs(i, j):
            if i == 1:
                if j == 0:
                    return 1
                else:
                    return 0
            if j < 0:
                return 0
            return (dfs(i, j - 1) + dfs(i - 1, j) - dfs(i - 1, j - i)) % base
        return dfs(n, k)
